算法设计与分析[0009] Dynamic Programming(II)(Maximum Sum/Product Subarray)

 本文通过 53. Maximum Subarray & 152. Maximum Product Subarray 分析根据动态规划思路进行问题求解中的一个关键环节:子问题的拆分和求解。

Problem Description

  • 两道题解决的问题相似,都是求解给定序列中满足某种数学特征(和最大/乘积最大)的子序列,虽然不需要将该子序列输出。

Find the contiguous subarray within an array(containing at least one number) which has the largest sum/product.

  • For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.
  • For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.
  • 留意的关键字眼是:containing at least one number,所以给定序列至少有一个元素,这也启发我们可以将其作为特殊处理。

53. Maximum Subarray 解题思路

  • 思路一:$sums[j]$ 为序列前 j 个元素的最大子段和作为求解的子问题,则 $sum[n]$ 则为问题的答案。然而,如何利用 $sums[1, 2, …, j-1]$ 对 $sums[j]$ 进行求解呢?显然需要知道前 j 个元素的最大字段和的子段起始和终止位置,求解这个子问题的状态迁移显然比较复杂。
  • 换一种思路。思路二:$sums[j]$ 为以第 j 个元素为结尾的子段的最大子段和作为求解的子问题,$max_{1 \leq j \leq n}(sums[j])$ 即为整个序列的最大子段和。而通过 $sums[j-1]$ 和当前元素 $nums[j]$ 即可计算以第 j 个元素为结尾的最大子段和 $sums[j]$,状态转移方程 如下:
    $$ sums[j+1] = \begin{cases} nums[j+1]      sums[j] \lt 0 \cr sums[j] + nums[j+1] others \end{cases}$$
  • 根据思路二,53. Maximum Subarray 解答如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int SizeofNums = nums.size();
if(SizeofNums == 1) {
return nums[0];
}
int sums[SizeofNums];
sums[0] = nums[0];
for(int i=1; i<SizeofNums; i++) {
// sums[i]: The largest sum of subarray ending with the i-th element
sums[i] = sums[i-1]<0 ? nums[i] : sums[i-1]+nums[i];
}

// The largest sum of the whole array
int largestSum = sums[0];
for(int i=1; i<SizeofNums; i++) {
if(largestSum < sums[i]) {
largestSum = sums[i];
}
}

return largestSum;
}
};
  • 为了得到 largestSum 对应的子序列,我们可以通过变量 startIdx 记录以第 j 个元素结尾(endIdx)的最大子段和对应子序列的起始位置,$nums[startIdx, …, endIdx]$ 即为对应的子序列;另外,考虑到当前状态只与前一个状态有关,所以可以使用变量代替数组,节省内存,同时,避免获取The largest sum of the whole array 时的重复循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int SizeofNums = nums.size();
if(SizeofNums == 1) {
return nums[0];
}
// largest sum for the subarray ending with current element
int curSum = nums[0];
// largest sum of subarray for the whole array
int largestSum = curSum;
// subarray[startIdx, endIdx] with largest sum for the whole array
int startIdx = 0, endIdx = 0;
for(int i=1; i<SizeofNums; i++) {
if(curSum < 0) {
curSum = nums[i];
startIdx = i;
}
else {
curSum = curSum + nums[i];
}

if(curSum > largestSum) {
largestSum = curSum;
endIdx = i;
}
}

return largestSum;
}
};

152. Maximum Product Subarray 解题思路

  • 这一题的解题流程与上一题基本类似,但是要解决的关键问题是:状态转移,即如何根据上一个子问题(以第 j 个元素为结尾的子段的max product)的答案推算出当前子问题的结果。
  • 从上一题的分析可以看出,当前子问题(以第 j 个元素为结尾的子段的max sum)的计算只需考虑上一个子问题的结果 $sum[j-1]$,$sum[j-1] < 0$,因为是加法,显然可以将子问题结果忽略;$sum[j-1] > 0$,$sum[j-1]$ 加上当前元素就是当前子问题的结果。
  • 类似的问题,只不过换成乘积,子问题的求解就变得复杂了,需要考虑以下几种情况:
    • 当前元素是正数,max product可能是正正得正的情况,因为都是整数,乘积>1,上一子问题的结果乘上当前元素即为当前子问题的答案
    • 当前元素是负数,max product可能是负负得正的情况,因此需要维护以第 j 个元素为结尾的子段的min product(很大可能是负数)
    • 另外,需要考虑上一个子问题的结果为0的情况
    • 总之,乘积的最大值为上述三种情况之一
      状态转移方程如下:
      $$ maxProducts[j+1] = max(maxProducts[j-1]*nums[j], minProducts[j-1]*nums[j], nums[j])$$
  • 152. Maximum Product Subarray 解答如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
int maxProduct(vector<int>& nums) {
int SizeofNums = nums.size();

if(SizeofNums == 1) {
return nums[0];
}
// The largest/least product of subarray ending with the i-th element
int maxProducts[SizeofNums];
int minProducts[SizeofNums];
maxProducts[0] = minProducts[0] = nums[0];
for(int i=1; i<SizeofNums; i++) {
// positive with positive, negative with negative, ignore previous zero
maxProducts[i] = max( max(maxProducts[i-1]*nums[i], minProducts[i-1]*nums[i]), nums[i]);
// positive with negative, negative with positive, ignore previous zero
minProducts[i] = min( min(maxProducts[i-1]*nums[i], minProducts[i-1]*nums[i]), nums[i]);
}

// getting the largest product for the whole array
int largestProduct = maxProducts[0];
for(int i=1; i<SizeofNums; i++) {
if(maxProducts[i] > largestProduct) {
largestProduct = maxProducts[i];
}
}

return largestProduct;
}
};
  • 与上一题类似,添加额外变量,也能实现节省内存,记录子段最大乘积对应子段($nums[startIdx, endIdx]$)的起始和终止位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
int maxProduct(vector<int>& nums) {
int SizeofNums = nums.size();

if(SizeofNums == 1) {
return nums[0];
}
// The largest/least product of subarray ending with the i-th element
int largestProduct = nums[0];
int leastProduct = nums[0];
// The largest product for the whole array
int maxProduct = largestProduct;
// subarray[startIdx, endIdx] with largest product for the whole array
int startIdx = 0, endIdx = 0;
// start index for largestProduct/leastProduct
int startIdx_pos = startIdx, startIdx_neg = startIdx;

for(int i=1; i<SizeofNums; i++) {
int largestProduct_pre = largestProduct;
int leastProduct_pre = leastProduct;

// positive with positive, negative with negative, ignore previous zero
largestProduct = max( max(largestProduct_pre*nums[i], leastProduct_pre*nums[i]), nums[i]);
if((largestProduct_pre != nums[i]) && (largestProduct == nums[i])) {
startIdx_pos = i;
}

// positive with negative, negative with positive, ignore previous zero
leastProduct = min( min(largestProduct_pre*nums[i], leastProduct_pre*nums[i]), nums[i]);
if((leastProduct_pre != nums[i]) && (leastProduct == nums[i])) {
startIdx_neg = i;
}

if(largestProduct > maxProduct) {
maxProduct = largestProduct;
if(largestProduct_pre*nums[i] > leastProduct_pre*nums[i]) {
startIdx = startIdx_pos;
}
else {
startIdx = startIdx_neg;
}
endIdx = i;
}
}

return maxProduct;
}
};
文章目录
  1. 1. Problem Description
  2. 2. 53. Maximum Subarray 解题思路
  3. 3. 152. Maximum Product Subarray 解题思路